package Algorithm.Sort;

import java.util.Arrays;

/**
 * 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
 * 若将两个有序表合并成一个有序表，称为二路归并。
 */
public class MergeSort {
    //交换两个元素
    public static void swap(int[] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //  归并排序
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length - 1);
    }
    // 在arr[l...r]进行归并排序,整个arr经过函数后就是一个已经有序的数组
    private static void mergeSortInternal(int[] arr, int l, int r) {
        if (l >= r) {
            // 当前数组只剩下一个元素,归过程就结束了
            return;
        }
        int mid = l + ((r - l) >> 1);
        // 将原数组拆分为左右两个小区间，分别递归进行归并排序
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        // merge  拆分结束，合并两个数组
        merge(arr,l,mid,r);
    }
    // 合并两个子数组arr[l..mid] 和 arr[mid + 1...r]
    // 为一个大的有序数组arr[l...r]
    private static void merge(int[] arr, int l, int mid, int r) {
        // 先创建一个新的临时数组aux
        int[] aux = new int[r - l + 1];
        // 将arr元素值拷贝到aux上
        for (int i = 0; i < aux.length; i++) {
            // 每次区间起始位置不同  因此 aux[i]对应arr[i+l]
            aux[i] = arr[i + l];
        }
        // 合并两个区间，i就是左侧小数组的开始索引，第一个区间
        int i = l;
        // j就是右侧小数组的开始索引
        int j = mid + 1;
        int count=0;
        // k表示当前正在合并的原数组的索引下标
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左侧区间已经被处理完毕，只需要将右侧区间的值拷贝原数组即可
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[k] = aux[i - l];
                count=
                        i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 此时左侧区间的元素值较小，相等元素放在左区间，保证稳定性
                arr[k] = aux[i - l];
                i ++;
            }else {
                // 右侧区间的元素值较小
                arr[k] = aux[j - l];
                count++;
                j ++;
            }
        }
    }
    // 归并排序，小区间使用插入排序
    public static void insertionSort(int[] arr,int l,int r){
        for (int i = l; i < arr.length; i++) {
            for (int j = i; j-1>0; j--) {
                if (arr[j]>arr[j-1]){
                    break;
                }
                if(arr[j]<arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }
    /**
     * 归并排序的迭代写法
     * @param arr
     */
    public static void mergeSortNonRecursion(int[] arr) {
        // 最外层循环表示每次合并的子数组的元素个数
        for (int sz = 1; sz <= arr.length; sz += sz) {
            // 内层循环的变量i表示每次合并的开始索引
            // i + sz 就是右区间的开始索引，i + sz < arr.length说明还存在右区间
            for (int i = 0; i + sz < arr.length ; i += sz + sz) {
                merge(arr,i,i + sz - 1,Math.min(i + sz + sz - 1,arr.length - 1));
            }
        }
    }
    public static void main(String[] args) {
        int[] arr2={9,1,5,8,3,7,4,6,2,};
        mergeSort(arr2);
        System.out.println(Arrays.toString(arr2));

    }
}
